# 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
#  
#  
#  
# 
#  示例 1： 
# 
#  
# 输入：head = [1,2,3,4,5]
# 输出：[5,4,3,2,1]
#  
# 
#  示例 2： 
# 
#  
# 输入：head = [1,2]
# 输出：[2,1]
#  
# 
#  示例 3： 
# 
#  
# 输入：head = []
# 输出：[]
#  
# 
#  
# 
#  提示： 
# 
#  
#  链表中节点的数目范围是 [0, 5000] 
#  -5000 <= Node.val <= 5000 
#  
# 
#  
# 
#  进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？ 
#  
#  
#  Related Topics 链表 
#  👍 1704 👎 0


from typing import List


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head



# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


"""
1. 迭代 a->b->c a->None b->c  b->a->None
2. 递归 a->b->c
    new_head = c, head = b a->b<-c
    new_head = c, head = a a<-b<-c
     
                       
"""

# def reverseList(self, head: ListNode) -> ListNode:
#     prev = None
#     current = head
#     while current:
#         next = current.next
#         current.next = prev
#         prev = current
#         current = next
#     return prev

# def reverseList(self, head: ListNode) -> ListNode:
#     if head is None or head.next is None:
#         return head
#     new_head = self.reverseList(head.next)
#     head.next.next = head
#     head.next = None
#     return new_head


if __name__ == '__main__':
    s = Solution()
    # [1,2,3,4,5]
    h = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    r = s.reverseList(h)
    while r:
        log(r.val)
        r = r.next
